import java.util.Stack;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 86132
 * Date: 2022-03-16
 * Time: 17:30
 */
public class Sort {
    public static void quickSort(int[] array){
        quick(array,0,array.length-1);
    }

    public static void quick(int[] array,int left,int right){
        if(left>=right){//递归终止条件
            return;
        }

        //优化：如果区间内的数据，在排序的过程中，小于某个范围了，可以使用直接插入排序,就不用快排了
        if(right-left+1<=40){
            insertSort(array,left,right);//直接插入排序
            return;
        }

        int midValIndex=findMidValIndex(array,left,right);//找到中间大小的下标
        swap(array,midValIndex,left);//将这个值与最左边的位置值交换，


        int pivot=partition(array,left,right);
        quick(array,left,pivot-1);
        quick(array,pivot+1,right);
    }
//直接插入排序
    public static void insertSort(int[]array,int start,int end) {
        for (int i = 1; i <= end; i++) {
            int tmp = array[i];
            int j = i - 1;
            for (; j >= start; j--) {
                if (array[j] > tmp) {
                    array[j + 1] = array[j];
                } else {
                    break;
                }
            }
            array[j + 1] = tmp;
        }
    }
    private static int findMidValIndex(int[]array,int start,int end){
        int mid=start+((end-start)>>>1);//求中间位置mid，然后找start，mid，end的中间大小的值
        if(array[start]<array[end]){
            if(array[mid]<array[start]){
                return start;
            }else if(array[mid]>array[end]){
                return end;
            }else{
                return mid;
            }
        }else{//array[start]>array[end]
            if(array[mid]>array[start]){
                return start;
            }else if(array[mid]<array[end]){
                return end;
            }else{
                return mid;
            }
        }
    }

    public static void swap(int[]array,int i,int j){//交换函数
        int tmp=array[i];
        array[i]=array[j];
        array[j]=tmp;
    }

    private static int partition(int[]array,int start,int end){
        int tmp=array[start];
        while(start<end){
            while(start<end&&array[end]>=tmp){
                end--;
            }
            //此时end下标遇到了<tmp的值
            array[start]=array[end];
            while(start<end&&array[start]<=tmp){
                start++;
            }
            //此时start下标遇到了>tmp的值
            array[end]=array[start];
        }
        array[start]=tmp;//将tmp放入相遇位置
        return start;
    }




    //非递归实现快排
    public static void quickSort1(int[] array){
        Stack<Integer> stack=new Stack<>();
        int left=0;
        int right=array.length-1;
        int pivot=partition(array,left,right);//找基准
        if(pivot>left+1){//说明左边有2个元素
            stack.push(left);
            stack.push(pivot-1);
        }
        if(pivot<right-1){//说明右边有两个元素
            stack.push(pivot+1);
            stack.push(right);
        }
        while(!stack.isEmpty()){
            right=stack.pop();//先弹出的是右边的
            left=stack.pop();//后弹出的是左边的
            pivot=partition(array,left,right);
            if(pivot>left+1){//说明左边有2个元素
                stack.push(left);
                stack.push(pivot-1);
            }
            if(pivot<right-1){//说明右边有两个元素
                stack.push(pivot+1);
                stack.push(right);
            }
        }
    }


    //合并两个有序(从小到大)数组
    public static int[] mergeArray(int[] array1,int[] array2){
        int [] tmp=new int[array1.length+array2.length];//创建一个大小为array1和array2长度和的数组tmp
        int k=0;//用K遍历tmp
        int s1=0;
        int e1=array1.length-1;
        int s2=0;
        int e2=array2.length-1;
        while(s1<=e1&&s2<=e2){
            if(array1[s1]<array2[s2]){
                tmp[k]=array1[s1];
                k++;
                s1++;
            }else{
                tmp[k]=array2[s2];
                k++;
                s2++;
            }
        }
        while(s1<=e1){//说明此时array1中还有元素
            tmp[k++]=array1[s1++];
        }
        while(s2<=e2){//说明此时array2中还有元素
            tmp[k++]=array1[s2++];
        }
        return tmp;
    }


    //归并
    public static void mergeSort(int[] array){
        mergeSortInternal(array,0,array.length-1);
    }

    private static void mergeSortInternal(int[] array,int low,int high){
        if(low>=high){
            return;
        }
        int mid=low+((high-low)>>>1);//找中间位置
        mergeSortInternal(array,low,mid);//递归左边
        mergeSortInternal(array,mid+1,high);//递归右边
        merge(array,low,mid,high);//将左边为low，右边为mid的数组和左边为mid+1，右边为high的数组排序合并起来
    }

    public static void merge(int[] array,int low,int mid,int high){//合并两个升序舒徐
        int[] tmp=new int[high-low+1];//创建一个大小为两个数组长度和的数组tmp
        int k=0;//用K遍历tmp
        int s1=low;
        int e1=mid;
        int s2=mid+1;
        int e2=high;
        while(s1<=e1&&s2<=e2){
            if(array[s1]<array[s2]){
                tmp[k]=array[s1];
                k++;
                s1++;
            }else{
                tmp[k]=array[s2];
                k++;
                s2++;
            }
        }
        while(s1<=e1){//说明此时array1中还有元素
            tmp[k++]=array[s1++];
        }
        while(s2<=e2){//说明此时array2中还有元素
            tmp[k++]=array[s2++];
        }
        //拷贝tmp数组的元素，放入原来的数组array中
        for (int i = 0; i < k; i++) {
            array[i+low]=tmp[i];
        }

    }


}

